/*
 * @lc app=leetcode.cn id=494 lang=typescript
 *
 * [494] 目标和
 */

// @lc code=start
function findTargetSumWays(nums: number[], target: number): number {
  let sum = 0;
  for (const num of nums) {
    sum += num;
  }

  const diff = sum - target;
  // 如果差值小于0，表示数组总和小于target，不能形成组合
  // 如果插值取模不等于0，表示当前不符合题意的整数数组
  if (diff < 0 || diff % 2 !== 0) {
    return 0;
  }

  const n = nums.length;
  const neg = diff / 2;
  // dp[i][j]，在前i个元素中选取若干元素，使元素之和等于j的方案数量。
  const dp = new Array(n + 1).fill(0).map(() => new Array(neg + 1).fill(0));
  // base case，0个元素中选取元素之和等于0，有1个方案
  dp[0][0] = 1;

  for (let i = 1; i <= n; i++) {
    let num = nums[i - 1];
    for (let j = 0; j <= neg; j++) {
      dp[i][j] = dp[i - 1][j];
      if (j >= num) {
        dp[i][j] += dp[i - 1][j - num];
      }
    }
  }

  return dp[n][neg];
}
// @lc code=end
